Mutual recursion

 ( Theory Of Computation ) 

In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or datatypes, are defined in terms of each other.Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes, Cristóbal Pareja-Flores (2002), 'A Gentle Introduction to Mutual Recursion', Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain. Mutual recursion is very common in functional programming and in some problem domains, such as recursive descent parsers, where the datatypes are naturally mutually recursive.

f: [t[1], ..., t[k]]
t: v f
     

This mutually recursive definition can be converted to a singly recursive definition by Inline expansion the definition of a forest:

t: v [t[1], ..., t[k]]
     

In Standard ML, the tree and forest datatypes can be mutually recursively defined as follows, allowing empty trees: datatype 'a tree = Empty | Node of 'a * 'a forest and 'a forest = Nil | Cons of 'a tree * 'a forest

As with directly recursive functions, a wrapper function may be useful, with the mutually recursive functions defined as within its scope if this is supported. This is particularly useful for sharing state across a set of functions without having to pass parameters between them.

   if (n == 0)
       return true;
   else
       return is_odd(n - 1);
     

   if (n == 0)
       return false;
   else
       return is_even(n - 1);
     

These functions are based on the observation that the question is 4 even? is equivalent to is 3 odd?, which is in turn equivalent to is 2 even?, and so on down to 0. This example is mutual single recursion, and could easily be replaced by iteration. In this example, the mutually recursive calls are , and tail call optimization would be necessary to execute in constant stack space. In C, this would take O( n) stack space, unless rewritten to use jumps instead of calls." Mutual Tail-Recursion" and " Tail-Recursive Functions", A Tutorial on Programming Features in ATS, Hongwei Xi, 2010 This could be reduced to a single recursive function is_even. In that case, is_odd, which could be inlined, would call is_even, but is_even would only call itself.

As a more general class of examples, an algorithm on a tree can be decomposed into its behavior on a value and its behavior on children, and can be split up into two mutually recursive functions, one specifying the behavior on a tree, calling the forest function for the forest of children, and one specifying the behavior on a forest, calling the tree function for the tree in the forest. In Python: def f_tree(tree) -> None:

   f_value(tree.value)
   f_forest(tree.children)
     

def f_forest(forest) -> None:

   for tree in forest:
       f_tree(tree)
     

Using the Standard ML datatype above, the size of a tree (number of nodes) can be computed via the following mutually recursive functions: fun size_tree Empty = 0

 | size_tree (Node (_, f)) = 1 + size_forest f
     

 | size_forest (Cons (t, f')) = size_tree t + size_forest f'
     

A more detailed example in Scheme, counting the leaves of a tree: (define (count-leaves tree)

 (if (leaf? tree)
     1
     (count-leaves-in-forest (children tree))))
     

(define (count-leaves-in-forest forest)

 (if (null? forest)
     0
     (+ (count-leaves (car forest))
        (count-leaves-in-forest (cdr forest)))))
     

These examples reduce easily to a single recursive function by inlining the forest function in the tree function, which is commonly done in practice: directly recursive functions that operate on trees sequentially process the value of the node and recurse on the children within one function, rather than dividing these into two separate functions.

Mutual recursion can also implement a finite-state machine, with one function for each state, and single recursion in changing state; this requires tail call optimization if the number of state changes is large or unbounded. This can be used as a simple form of cooperative multitasking. A similar approach to multitasking is to instead use which call each other, where rather than terminating by calling another routine, one coroutine yields to another but does not terminate, and then resumes execution when it is yielded back to. This allows individual coroutines to hold state, without it needing to be passed by parameters or stored in shared variables.

There are also some algorithms which naturally have two phases, such as minimax (min and max), which can be implemented by having each phase in a separate function with mutual recursion, though they can also be combined into a single function with direct recursion.

Fractals can be computed (up to a given resolution) by recursive functions. This can sometimes be done more elegantly via mutually recursive functions; the Sierpiński curve is a good example.

Some programming styles discourage mutual recursion, claiming that it can be confusing to distinguish the conditions which will return an answer from the conditions that would allow the code to run forever without producing an answer. Peter Norvig points to a design pattern which discourages the use entirely, stating: Solving Every Sudoku Puzzle

Any mutual recursion between two procedures can be converted to direct recursion by inlining the code of one procedure into the other. On the Conversion of Indirect to Direct Recursion by Owen Kaser, C. R. Ramakrishnan, and Shaunak Pawagi at State University of New York, Stony Brook (1993) If there is only one site where one procedure calls the other, this is straightforward, though if there are several it can involve code duplication. In terms of the call stack, two mutually recursive procedures yield a stack ABABAB..., and inlining B into A yields the direct recursion (AB)(AB)(AB)...

Alternately, any number of procedures can be merged into a single procedure that takes as argument a variant record (or algebraic data type) representing the selection of a procedure and its arguments; the merged procedure then dispatches on its argument to execute the corresponding code and uses direct recursion to call self as appropriate. This can be seen as a limited application of defunctionalization. This translation may be useful when any of the mutually recursive procedures can be called by outside code, so there is no obvious case for inlining one procedure into the other. Such code then needs to be modified so that procedure calls are performed by bundling arguments into a variant record as described; alternately, wrapper procedures may be used for this task.

• Cycle detection (graph theory)
• Recursion (computer science)
• Circular dependency

• (1999). 9780262082815, MIT Press. ISBN 9780262082815
• Graham Hutton (2025). 9780521692694, Cambridge University Press. ISBN 9780521692694

• Mutual recursion at Rosetta Code
• " Example demonstrating good use of mutual recursion", " Are there any example of Mutual recursion?", Stack Overflow